Shellsort

 ( Comparison Sorts ) 

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be understood as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.

The algorithm was first published by Donald Shell in 1959, and has nothing to do with shells.Some older textbooks and references call this the "Shell–Metzner" sort after Marlene Metzner Norton, but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it." See

Robert Sedgewick (1998). 9780201314526, Addison-Wesley. . ISBN 9780201314526
 Beginning with large values of ''h'' allows elements to move long distances in the original list, reducing large amounts of disorder quickly, and leaving less work for smaller ''h''-sort steps to do.
     
 (1996). 9787302024125, Prentice Hall. ISBN 9787302024125 If the list is then ''k-sorted'' for some smaller integer ''k'', then the list remains ''h''-sorted. A final sort with ''h'' = 1 ensures the list is fully sorted at the end, but a judiciously chosen decreasing sequence of ''h'' values leaves very little work for this final pass to do.
     

   // Do a gapped insertion sort for every element in gaps
   // Each loop leaves a[0..gap-1] in gapped order
   for (int i = gap; i < n; ++i)
   {
       // save a[i] in temp and make a hole at position i
       int temp = a[i];
       // shift earlier gap-sorted elements up until the correct location for a[i] is found
       for (int j = i; (j >= gap) && (a[j - gap] > temp); j -= gap)
       {
           a[j] = a[j - gap];
       }
       // put temp (the original a[i]) in its correct location
       a[j] = temp;
   }
     

       \left\lfloor\frac{N}{2}\right\rfloor
 
     

       \; \; 2 \left\lfloor\frac{N}{4}\right\rfloor + 1
 
     

          &\prod\limits_I a_q, \hbox{where} \\
 a_0 = {} &3 \\
 a_q = {} &\min\left\{n \in \mathbb{N}\colon n \ge \left(\frac{5}{2}\right)^{q+1}, \forall p\colon 0 \le p < q \Rightarrow \gcd(a_p, n) = 1\right\} \\
   I = {} &\left\{0 \le q < r \mid q \neq \frac{1}{2}\left(r^2 + r\right) - k \right\} \\
   r = {} &\left\lfloor \sqrt{2k + \sqrt{2k}} \right\rfloor
     

 9\left(2^{k} - 2^\frac{k}{2}\right) + 1 & k\text{ even}, \\
 8 \cdot 2^{k} - 6 \cdot 2^{(k+1)/2} + 1         & k\text{ odd}
     

       \left\lfloor \frac{5N-1}{11} \right\rfloor
 
     

With respect to the average number of comparisons, Ciura's sequence has the best known performance; gaps greater than 701 were not determined but the sequence can be further extended according to the recursive formula $h\_k\; =\; \backslash lfloor\; 2.25\; h\_\{k-1\}\; \backslash rfloor$.

Tokuda's sequence, defined by the simple formula $h\_k\; =\; \backslash lceil\; h\text{'}\_k\; \backslash rceil$, where $h\text{'}\_k\; =\; 2.25\; h\text{'}\_\{k-1\}\; +\; 1$, $h\text{'}\_1\; =\; 1$, can be recommended for practical applications.

If the maximum input size is small, as may occur if Shellsort is used on small subarrays by another recursive sorting algorithm such as quicksort or merge sort, then it is possible to tabulate an optimal sequence for each input size. Additional commentary at Fastest gap sequence for shell sort? (23 May 2018). For N = 128 and N = 1000, Ciura empirically found that (1, 4, 9, 24, 85) and (1, 4, 10, 23, 57, 156, 409, 995) made the fewest number of comparisons on average respectively.

Mark Allen Weiss proved that Shellsort runs in O( N log N) time when the input array is in reverse order.

With respect to the average number of operations, none of the proven results concerns a practical gap sequence. For gaps that are powers of two, Espelid computed this average as $0.5349N\backslash sqrt\{N\}-0.4387N-0.097\backslash sqrt\{N\}+O(1)$. The quoted result is equation (8) on p. 399. Donald Knuth determined the average complexity of sorting an N-element array with two gaps ( h, 1) to be $\backslash frac\{2N^2\}\{h\}\; +\; \backslash sqrt\{\backslash pi\; N^3\; h\}$. It follows that a two-pass Shellsort with h = Θ( N^1/3) makes on average O( N^5/3) comparisons/inversions/running time. Andrew Yao found the average complexity of a three-pass Shellsort. His result was refined by Svante Janson and Knuth: the average number of comparisons/inversions/running time made during a Shellsort with three gaps ( ch, cg, 1), where h and g are coprime, is $\backslash frac\{N^2\}\{4ch\}\; +\; O(N)$ in the first pass, $\backslash frac\{1\}\{8g\}\backslash sqrt\{\backslash frac\{\backslash pi\}\{ch\}\}(h\; -\; 1)N^\{3/2\}\; +\; O(hN)$ in the second pass and $\backslash psi(h,\; g)N\; +\; \backslash frac\{1\}\{8\}\backslash sqrt\{\backslash frac\{\backslash pi\}\{c\}\}(c\; -\; 1)N^\{3/2\}\; +\; O\backslash left((c\; -\; 1)gh^\{1/2\}N\backslash right)\; +\; O\backslash left(c^2g^3h^2\backslash right)$ in the third pass. ψ( h, g) in the last formula is a complicated function asymptotically equal to $\backslash sqrt\{\backslash frac\{\backslash pi\; h\}\{128\}\}g\; +\; O\backslash left(g^\{-1/2\}h^\{1/2\}\backslash right)\; +\; O\backslash left(gh^\{-1/2\}\backslash right)$. In particular, when h = Θ( N^7/15) and g = Θ( N^1/5), the average time of sorting is O( N^23/15).

Based on experiments, it is conjectured that Shellsort with Hibbard's gap sequence runs in O( N^5/4) average time, and that Gonnet and Baeza-Yates's sequence requires on average 0.41 N ln  N (ln ln  N + 1/6) element moves. Approximations of the average number of operations formerly put forward for other sequences fail when sorted arrays contain millions of elements.

The graph below shows the average number of element comparisons use by various gap sequences, divided by the theoretical lower bound, i.e. log₂ N!. Ciuria's sequence 1, 4, 10, 23, 57, 132, 301, 701 (labelled Ci01) has been extended according to the formula $h\_k\; =\; \backslash lfloor2.25\; h\_\{k-1\}\backslash rfloor$.

Applying the theory of Kolmogorov complexity, Jiang, Ming Li, and Vitányi proved the following lower bound for the order of the average number of operations/running time in a p-pass Shellsort: Ω( pN^{1+1/ p}) when p ≤ log₂ N and Ω( pN) when p > log₂ N. Therefore, Shellsort has prospects of running in an average time that asymptotically grows like N log N only when using gap sequences whose number of gaps grows in proportion to the logarithm of the array size. It is, however, unknown whether Shellsort can reach this asymptotic order of average-case complexity, which is optimal for comparison sorts. The lower bound was improved by Vitányi for every number of passes $p$ to $\backslash Omega\; (\; N\backslash sum\_\{k=1\}^p\; h\_\{k-1\}/h\_k\; )$ where $h\_0=N$. This result implies for example the Jiang-Li-Vitányi lower bound for all $p$-pass increment sequences and improves that lower bound for particular increment sequences. In fact all bounds (lower and upper) currently known for the average case are precisely matched by this lower bound. For example, this gives the new result that the Janson-Knuth upper bound is matched by the resulting lower bound for the used increment sequence, showing that three pass Shellsort for this increment sequence uses $\backslash Theta(N^\{23/15\})$ comparisons/inversions/running time. The formula allows us to search for increment sequences that yield lower bounds which are unknown; for example an increment sequence for four passes which has a lower bound greater than $\backslash Omega(pn^\{1+1/p\})\; =\; \backslash Omega(n^\{5/4\})$ for the increment sequence $h\_1\; =\; n^\{11/16\},$ $h\_2\; =\; n^\{7/16\},$ $h\_3\; =\; n^\{3/16\},$ $h\_4\; =\; 1$. The lower bound becomes $T\; =\; \backslash Omega(n\backslash cdot\; (n^\{1-11/16\}+n^\{11/16-7/16\}+n^\{7/16-3/16\}+n^\{3/16\})\; =\; \backslash Omega(n^\{1+5/16\})\; =\; \backslash Omega(n^\{21/16\}).$

The worst-case complexity of any version of Shellsort is of higher order: Plaxton, Bjorn Poonen, and Torsten Suel showed that it grows at least as rapidly as $\backslash Omega\backslash left(N\; \backslash left(\; \{\backslash log\; N\; \backslash over\; \backslash log\; \backslash log\; N\}\; \backslash right)^2\backslash right)$.

Shellsort can also serve as a sub-algorithm of introsort, to sort short subarrays and to prevent a slowdown when the recursion depth exceeds a given limit. This principle is employed, for instance, in the bzip2 compressor.

• Comb sort

• Donald E. Knuth (1997). 9780201896855, Addison-Wesley. ISBN 9780201896855
• Analysis of Shellsort and Related Algorithms, Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, September 1996.

• – graphical demonstration
• Shellsort with gaps 5, 3, 1 as a Hungarian folk dance